package algotithm.jianzhioffer.test47;

/**
 * @author zhouyanxiang
 * @Date 2021-03-2021/3/15-23:40
 * @Title 剑指 Offer 47. 礼物的最大价值
 */
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] grid = {
                {1,3,1},
                {1,5,1},
                {4,2,1}
        };
        int maxValue = solution.maxValue(grid);
        System.out.println(maxValue);
    }

    public int maxValue(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        for (int i = 1; i < n; i++) {
            grid[i][0] += grid[i-1][0];
        }
        for (int j = 1; j < m; j++) {
            grid[0][j] += grid[0][j-1];
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                grid[i][j] += Math.max(grid[i-1][j],grid[i][j-1]);
            }
        }
        return grid[n-1][m-1];
    }
}
